package interview;

import java.util.Arrays;

public class lc673 {
    public static void main(String[] args) {
        System.out.println(findNumberOfLIS(new int[]{1,3,5,4,7}));
    }
    public static int findNumberOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int[] count = new int[nums.length];
        int sum = 0;
        int t = 1;
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i])
                        count[i] = count[j];
                    if(dp[i] == dp[j] + 1)
                        count[i] += count[j];
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    t = Math.max(t, dp[i]);
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(dp[i] == t)
                sum += count[i];
        }
        return sum;
    }
}
